/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/3sum-smaller
   @Language: C++
   @Datetime: 19-04-19 17:31
   */

class Solution {
public:
	/**
	 * @param nums:  an array of n integers
	 * @param target: a target
	 * @return: the number of index triplets satisfy the condition nums[i] + nums[j] + nums[k] < target
	 */
	int threeSumSmaller(vector<int> &nums, int target) {
		// Write your code here
		int count=0;
		sort(nums.begin(), nums.end());
		for(int i=0; i<nums.size(); ++i){
			for(int j=i+1, k=nums.size()-1; j<k;){
				if(nums[i]+nums[j]+nums[k] < target){
					count+=k-j;
					++j;
				}
				else --k;
			}
		}
		return count;
	}
};
